#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
#define MAXN 1010
typedef __int64 I64;
 
struct EDGE{
    int to, next;
}edges[MAXN * MAXN];
int head[MAXN], ad, vis[MAXN], match[MAXN];
__int64 a[MAXN];
 
void clear(){
    ad = 0;
    memset(head, - 1, sizeof(head));
}
 
void insert(int x, int y){
    edges[ad].to = y; edges[ad].next = head[x]; head[x] = ad ++;
}
 
int find(int u){
    int i;
    for(i = head[u]; ~i; i = edges[i].next){
       int v = edges[i].to;
       if(!vis[v]){
           vis[v] = 1;
           if(match[v] == -1 || find(match[v])){
              match[v] = u;
              return 1;
           }
       }
    }
    return 0;
}
 
int main(){
    int CASE;
    int n, i, j;
    scanf("%d", &CASE);
    while(CASE --){
       scanf("%d", &n);
       for(i = 0; i < n; i ++)
           scanf("%I64d", &a[i]);
       clear();
       int m = 0;
       for(i = 0; i < n; i ++)
           if(a[i])
              for(j = 0; j < n; j ++)
                  if(i != j && a[j] == a[i]){
                     a[j] = 0;
                     m ++;
                  }
                  else
                     if(a[j] && i != j && a[j] % a[i] == 0) insert(i, j);
       int ans = 0;
       memset(match, -1, sizeof(match));
       for(i = 0; i < n; i ++){
           memset(vis, 0, sizeof(vis));
           if(find(i)) ans ++;
       }
       printf("%d\n", n - m - ans );
    }
    return 0;
}